#include <stdio.h>
#include <string.h>

#define NODES_NR 64
typedef char node;
#define key(A) (A) // wyznaczony klucz
#define exch(A, B) { node t = A; A = B; B = t; } // zamiana wezlow
#define R 2
#define BYTE_PER_WORD 8

unsigned getbits(unsigned , int , int ); // n-bitowe pole wyciete z x od pozycji p [K&R]
unsigned digit(node , int d); // d-ty bit klucza key(a) dla wezla a
void lsdrsort(node* , int , int ); // sortowanie pozycyjne od cyfry najmniej znaczacej

int main()
{
  node v[NODES_NR]; // tablica elementow
  strcpy(v, "lsdsort"); 
  int n = strlen(v); // liczba elementow
  lsdrsort(v, 0, n); // sortowanie pozycyjne od cyfry najmniej znaczacej
  //int i; for (i = 1; i < n+1; i++) printf("%c", v[i]);
  return 0;
}

unsigned getbits(unsigned x, int p, int n)
{
  return (x>>(p+1-n)) & ~(~0<<n);
}

unsigned digit(node a, int d)
{
  return getbits(key(a), 7 - d, 1);
}

void lsdrsort(node a[], int l, int r)
{
  node aux[NODES_NR];
  int i, j, w, count[R+1]; 
  for (w = BYTE_PER_WORD-1; w >= 0; w--) {
    for (j = 0; j < R; j++) 
      count[j] = 0;
    for (i = l; i <= r; i++) 
      count[digit(a[i], w) + 1]++;
    for (j = 1; j < R; j++) 
      count[j] += count[j-1];
    for (i = l; i <= r; i++) 
      aux[count[digit(a[i], w)]++] = a[i];
    for (i = l; i <= r; i++) 
      a[i] = aux[i];
  }
} 

